package queen;

import java.util.*;

public class 打开转盘锁 {
    public static void main(String[] args) {
        Solution solution = new Solution();
        int i = solution.openLock(new String[]{"0102", "0090"}, "1011");
        System.out.println(i);

    }

    static class Solution{
    public int openLock(String[] deadends, String target) {
        Set<String> set = new HashSet<>(Arrays.asList(deadends));//将死亡数组放入哈希set中
        //"0000"是根节点 以此开始遍历
        String startstr="3000";
        if (set.contains(startstr)){    //如果死亡数组中有"0000"则无法解锁
            return -1;
        }
        //创建队列
        Queue<String> queue = new LinkedList<>();
        //记录访问过的节点
        Set<String> visited = new HashSet<>();
        queue.offer(startstr);      //初始化队列
        visited.add(startstr);      //初始化哈希set

        //树的层数
        int level=0;
        while(!queue.isEmpty()){
            //每层子节点的个数
            int size = queue.size();

            while(size-- >0){
                //每个节点的值
                String str = queue.poll();
                //对于每个节点值，对四个树分别都加1和减1，如0001，0009，0010，0090....
                //此时每个节点又会产生8个子节点
                for (int i = 0;i<4;i++){
                    char ch = str.charAt(i);
                    //strAdd表示加的结果,strSub表示减1的结果
                    String strAdd = str.substring(0, i) + (ch == '9' ? '0' : ch - '0' + 1) + str.substring(i + 1);
                    String strSub = str.substring(0, i) + (ch == '0' ? '9' : ch - '0' - 1) + str.substring(i + 1);
                    //如果找到就直接返回
                    if (str.equals(target)){
                        return level;
                    }
                    //不能包含死亡数字也不包含访问过的字符串
                    if (!visited.contains(strAdd) && !set.contains(strAdd)){
                        queue.offer(strAdd);    //存入队列，等待处理
                        visited.add(strAdd);    //进入已访问集合
                    }
                    if (!visited.contains(strSub) && !set.contains(strSub)){
                        queue.offer(strSub);    //存入队列，等待处理
                        visited.add(strSub);    //进入已访问集合
                    }

                }

            }
            level++;

        }

        return -1;
    }
    }
}
